package 回溯;

import java.util.LinkedList;
import java.util.List;

//77 组合
public class Solution1 {
    public List<List<Integer>> combine(int n, int k) {
        dfs(1,new LinkedList<>(),n,k);
        return res;
    }
    List<List<Integer>> res = new LinkedList<>();
    void dfs(int index, List<Integer> path, int n, int k){
        if(path.size()+n-index+1<k) return; //剪枝
        if(path.size()==k){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=index;i<=n;i++){
            path.add(i);
            dfs(i+1,path,n,k);
            path.remove(path.size()-1);
        }
        return;
    }
}
